package newcoder_exp.justPractise;

import java.util.*;

import org.junit.Test;

public class Nc55 {
   /* 
        使用前缀树来解决
   */ 
    public String longestCommonPrefix (String[] strs) {
        PTree pt = new PTree();
        for (String s: strs) {
            pt.insert(s);
        }
        return "A";
    }

    class PTree {
        PTNode head;
        
        public PTree() {
            this.head = new PTNode();
        }

        public void insert(String s) {
            int idx;
            PTNode n = head, p = head;
            for (char c: s.toCharArray()) {
                idx = c - 'a';
                if (p.nexts[idx] == null) {
                    p.nexts[idx] = new PTNode();
                }
                n = p.nexts[idx];
                n.times++;
                if (p.maxPath != idx && n.times > p.nexts[p.maxPath].times) {
                    p.maxPath = idx;
                }
                p = n;
            }
            n.isEnd = true;
        }
    }

    class PTNode {
        int maxPath;
        boolean isEnd;
        PTNode[] nexts;
        int times;

        public PTNode() {
            this.maxPath = 0;
            this.nexts = new PTNode[26];
        }
    }

    @Test
    public void test() {
        String[] strs = {"abca","abc","abca","abc","abcc"};
        longestCommonPrefix(strs);
    }
}